NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/11631

Internet Message Format | 1996-08-05 | 4.2 KB

Path: keats.ugrad.cs.ubc.ca!not-for-mail
From: [e-mail] (Kazimir Kylheku)
Newsgroups: comp.lang.c
Subject: Re: binary tree question
Date: 25 Mar 1996 07:54:27 -0800
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Message-ID: <[e-mail]>
References: <4isglj$[e-mail]> <[e-mail]> <4ivpff$[e-mail]>
NNTP-Posting-Host: keats.ugrad.cs.ubc.ca

In article <4ivpff$[e-mail]>, J. A. McNamara <[e-mail]> wrote:
>Kazimir Kylheku ([e-mail]) wrote:
>: This is not a pure ``inorder'' traversal. The nodes are being added to the
>: linked list in order, but you are freeing in post-order (children are visited
>: first, then you free the parent).
>
>hmmm, yeah, I see yr point.  would that affect anything?  I think I did it
>that way originally because I was freeing the children, so I wanted it in
>a safe place.

No. It is perfectly valid, in a binary tree traversal function, to effect
three orders of traversal. It's just a matter of where you put the statements.
The things you want to be done in order, you put between the recursive calls to
process the left and right child. The things you want in post-order (children
visited before parent), you put after these two statements. Things to be done
in pre-order you put at the beginning, before processing the children. You
get all three orders simultaneously.

>:  >free(tn->l); tn->l=NULL;
>:  >free(tn->r); tn->r=NULL;
>:  >
>:  >. . .  which gave me some serious garbage, though I'm not quite sure why.
>
>: Because you probably did not check whether the children are null pointers or
>: not, only whether tn is a null pointer. Just because tn is a valid tree node
>: doesn't mean that tn->l or tn->r are.
>
>jesus, I'm really batting 1000 here.  I don't grok why that would give the
>list pointers to garbage, though; that stuff was postorder, just like the
>free() in the whole function I posted.  ??

Because if you call free() on tn->l or tn->r, and they happen to be invalid
garbage pointers, you are calling for undefined behavior. Anything could
happen: malloc heap corruption, etc.

>: The above modification will also fail to
>: free the root node.
>
>ah!  small potatoes, but worth noting.

It could lead to a memory leak if you make and destroy a lot of trees at some
higher level of the code.

>: Your code appears fine. That it's not actually freeing memory is not
>: surprising. Many free() implementations don't free memory, they only return
>: free blocks to a list from where subsequent malloc() invocations can obtain
>: memory quickly.
>
>how isn't that freeing?  if this'll clarify things any, I want to free the
>tree to make room for the list, so one shrinks as the other grows.  I'd
>guess (!) that the malloc() in the addlink() function would then pull
>memory off that list, right?   (and both structs are the same size, three
>pointers).  does it then not free the memory for *non*-malloc() purposes?
>Or only sorta free it?  This is something I'm kinda foggy about in
>general.

That is correct.  The memory that is deallocated with free() is generally not
available for non-malloc purposes. It _can_ be, but it typically isn't.

In standard C, there is no way to have any other ``non malloc'' purpose anyway.
Malloc is the only way to obtain pieces of dynamic memory. To ``really free''
memory would mean that when you call free(), memory is actually returned to the
operating system so that it can be used for other programs. On systems with a
global heap or with virtual memory, this is possible.

Even on virtual memory systems like UNIX, though, free() does not generally do
this.

Repeated use of malloc() and free() can fragment your memory, meaning that gaps
have been created  between allocated segments that are too small to be useful
and can't be coalesced.

Have a look at K&R2, section 8.7 Example---A Storage Allocator.  It shows a
simple C implementation of malloc() and free(). N.B.: you cannot write your own
function called malloc() as the book suggests, for it is a reserved symbol
according to ANSI. The book is wrong in this respect.




>
>--
>                          j a mcnamara  aramancm a j
>                      [e-mail]  moc.sxaten@mlurg


--